//给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
//
// 在执行上述操作后，返回包含相同字母的最长子字符串的长度。
//
//
//
// 示例 1：
//
//
//输入：s = "ABAB", k = 2
//输出：4
//解释：用两个'A'替换为两个'B',反之亦然。
//
//
// 示例 2：
//
//
//输入：s = "AABABBA", k = 1
//输出：4
//解释：
//将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
//子串 "BBBB" 有最长重复字母, 答案为 4。
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁵
// s 仅由大写英文字母组成
// 0 <= k <= s.length
//
// Related Topics 哈希表 字符串 滑动窗口 👍 596 👎 0

package leetcode.editor.cn;

@SuppressWarnings("all")
//Java：替换后的最长重复字符
public class 替换后的最长重复字符 {
    public static void main(String[] args) {
        Solution solution = new 替换后的最长重复字符().new Solution();
        // TO TEST
        int n = solution.characterReplacement("AABABBA", 1);
        System.out.println(n);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int characterReplacement(String s, int k) {

            if (s == null) {
                return 0;
            }
            int[] map = new int[26];
            char[] chars = s.toCharArray();
            int left = 0;
            int right = 0;
            int historyCharMax = 0;
            for (right = 0; right < chars.length; right++) {
                int index = chars[right] - 'A';
                map[index]++;
                historyCharMax = Math.max(historyCharMax, map[index]);
                if (right - left + 1 > historyCharMax + k) {
                    map[chars[left] - 'A']--;
                    left++;
                }
            }
            return chars.length - left;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
